class Solution {
    public int findKthLargest(int[] nums, int k) {
        return findKthLargestUseQuickSort(nums, 0, nums.length - 1, nums.length - k);
    }
    public int findKthLargestUseHeapSort(int[] nums, int k) {
        Queue<Integer> queue = new PriorityQueue<>(nums.length, (a, b) -> (b - a));
        for (int i = 0; i < nums.length; i++) {
            queue.offer(nums[i]);
        }
        for (int i = 0; i < k - 1; i++) {
            queue.poll();
        }
        return queue.peek();
    }
    private int findKthLargestUseQuickSort(int[] nums, int left, int right, int target) {
        if (left == right) return nums[left];
        int idx = partition(nums, left, right);
        if (idx < target) {
            return findKthLargestUseQuickSort(nums, idx + 1, right, target);
        } else {
            return findKthLargestUseQuickSort(nums, left, idx, target);
        }
    }
    private int partition(int[] nums, int left, int right) {
        int idx = left + (int)(Math.random() * (right - left + 1));
        int idxValue = nums[idx];
        while (left <= right) {
            while (nums[left] < idxValue) left++;
            while (nums[right] > idxValue) right--;
            if (left == right) break;
            if (left < right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left++;
                right--;
            }
        }
        return right;
    }
}
